package com.zp.self.module.level_4_算法练习.算法.双指针.快慢指针;

import com.zp.self.module.level_4_算法练习.数据结构.链表.ListNode;

/**
 * @author By ZengPeng
 */
public class 力扣_234_回文链表 {
    public static void main(String[] args) {

        ListNode n1 = new ListNode(1);
        n1.next= new ListNode(2);
        n1.next.next= new ListNode(3);
        n1.next.next.next= new ListNode(1);

        boolean listNode2 = isPalindrome(n1);
        System.out.println(listNode2);

    }

    /**
     * 题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
     * 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
     *
     * 分析：
     *      1.先利用迭代 翻转链表 ，得到一个新的链表，再遍历是否相同
     *      2.进阶的话
     *              异或操作 ==0  ？  那不行  不同的值异或也为0 啊
     *              1.快慢指针：找到中间值。
     *              2.倒转后半截
     *              3.开始对比慢指针与新指针的值
     *
     *
     * 边界值注意：
     *      1. [1,0,1]
     **/
    static boolean isPalindrome(ListNode head) {
        //快慢指针找到中间点
        if(head.next==null) return true;
        ListNode slow=head ,quick =head.next;
        while(quick.next!=null){
            slow = slow.next;
            quick=quick.next.next;
            if(quick==null) break;
        }
        //倒转后半截
        slow = slow.next;
        ListNode next = slow.next;
        slow.next=null;
        while(next!=null){
            ListNode next1 = next.next;
            next.next = slow;
            slow=next;
            next = next1;
        }
        //前后半截对比
        quick =head;
        while (slow!=null){
            if(slow.val !=quick.val) return false;
            slow = slow.next;
            quick=quick.next;
        }
        return true;
    }
}
